package leetcode.hard;

import leetcode.ListNode;

import java.util.PriorityQueue;

public class No23 {
    public static void main(String[] args) {

        leetcode.ListNode[] listNodes = new leetcode.ListNode[]{leetcode.ListNode.createByArray(new int[]{1, 4, 5}), leetcode.ListNode.createByArray(new int[]{1, 3, 4}), leetcode.ListNode.createByArray(new int[]{2, 6})};

        No23 no23 = new No23();
        leetcode.ListNode listNode = no23.mergeKLists(listNodes);
        leetcode.ListNode.print(listNode);
    }

    public leetcode.ListNode mergeKLists(leetcode.ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode head = new ListNode(-1);
        ListNode p = head;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (o1, o2) -> o1.val - o2.val);
        for (ListNode list : lists) {
            if (list != null) {
                queue.add(list);
            }
        }
        while (!queue.isEmpty()) {
            ListNode poll = queue.poll();
            p.next = poll;
            if (poll.next != null) {
                queue.add(poll.next);
            }
            p = p.next;
        }
        return head.next;
    }

}
